To harness modern multicore processors, it is imperative to develop parallelversions of fundamental algorithms. In this paper, we compare differentapproaches to parallel best-first search in a shared-memory setting. We presenta new method, PBNF, that uses abstraction to partition the state space and todetect duplicate states without requiring frequent locking. PBNF allowsspeculative expansions when necessary to keep threads busy. We identify and fixpotential livelock conditions in our approach, proving its correctness usingtemporal logic. Our approach is general, allowing it to extend easily tosuboptimal and anytime heuristic search. In an empirical comparison on STRIPSplanning, grid pathfinding, and sliding tile puzzle problems using 8-coremachines, we show that A*, weighted A* and Anytime weighted A* implementedusing PBNF yield faster search than improved versions of previous parallelsearch proposals.
展开▼
